package leetcode.sort;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author: feiwang_6
 * @create: 2020/7/19 19:53
 * @description:
 */
public class QuickSort {
    
    @Test
    public void test(){
        List<Integer> list = Arrays.asList(3, 6, 1, -2, -10, 0, 10, 2, 2, 2, 5, 0);
        List<Integer> list2 = Arrays.asList(3, 6, 1, -2, -10, 0, 10, 2, 2, 2, 5, 0);

        quickSort(list, 0, list.size() -1);
        System.out.println(list);
        int index = findMthEnum(list2, 10);
        System.out.println(index);
        System.out.println(list.get(index));
    }

    /**
     * 查找第M大个元素
     * @param list
     * @param m
     * @return
     */
    public int findMthEnum(List<Integer> list, int m){
        return selectQuery(list, 0, list.size()-1, list.size()-m);
    }
    
    public int selectQuery(List<Integer> list, int start, int end, int m){
        if(start > end){
            return -1;
        }
        int tag = list.get(start);
        int left = start;
        int right = end;
        while(left != right){
            if(list.get(right) >= tag){
                right--;
                continue;
            }
            if(list.get(left) <= tag){
                left++;
                continue;
            }
            if(list.get(left) > tag && list.get(right) < tag){
                swap(list, left, right);
            }
        }
        if(left == m){
            return left;
        }
        swap(list, start, left);
        return m > left ? selectQuery(list, left+1, end, m) : selectQuery(list, start, left-1, m);
    }
    
    /**
     * 快排
     * @param list
     * @param start
     * @param end
     */
    public void quickSort(List<Integer> list, int start, int end){
        if(start > end){
            return;
        }
        int tag = list.get(start);
        int i = start, j = end;
        while(i != j){
            if(list.get(j) >= tag){
                j--;
                continue;
            }
            if(list.get(i) <= tag){
                i++;
                continue;
            }
            if(list.get(j) < tag && list.get(i) > tag){
                swap(list, i, j);
            }
        }
        swap(list, start, i);
        //left
        quickSort(list, start, i-1);
        //right
        quickSort(list, i+1, end);
    }

    /**
     * 交换元素
     * @param list
     * @param i
     * @param j
     */
    public void swap(List<Integer> list, int i, int j){
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}
